﻿#define _CRT_SECURE_NO_WARNINGS
/*
  Definition for singly-linked list.
  struct ListNode
  {
      int val;
     struct ListNode *next;
  };
 */

//实现一种算法  找出单向链表中倒数第k个节点  返回该节点的值
//int kthToLast(struct ListNode* head, int k)
//{
//    //快慢指针  快指针先走k步  然后开始一起走
//    struct ListNode* fast = head, * slow = head;
//    //快指针先走k步
//    while (k--)
//    {
//        //k--   就是走k步
//        fast = fast->next;
//    }
//    //开始同时走
//    while (fast)
//    {
//        slow = slow->next;
//        fast = fast->next;
//    }
//    return slow->val;    //返回的不应该是指针   而是指针指向的值  slow->val
//}


//链表的回文结构
/*
    对于链表  设计一个时间复杂度O(N)  额外空间复杂度O(1)的算法   判断其是否为回文结构
    给定一个链表头指针A  返回一个bool值  代表其是否为回文结构  保证链表长度小于等于900     从中间劈开是对称的  回文
    C++兼容C语言
    做法：先找中间节点（偶数个节点的中间节点返回后一个）  后半段进行逆置   然后和之前的链表进行对比
*/
//class PalindromeList {
//public:
//    //快慢指针对链表的中间节点进行查找
//  //创建找中间节点的函数  存储节点  传参传指向头结点的结构体指针
//    struct ListNode* middleNode(struct ListNode* head)
//    {
//        struct ListNode* fast = head, * slow = head;    //这里也要带struct
//        while (fast && fast->next)   //注意这里要判断fast 和 fast下一个是否为空  因为一下走两次
//        {
//            slow = slow->next;
//            fast = fast->next->next;
//        }
//        return slow;
//    };
//
//    //对链表的逆置的函数   传参也传头结点  
//    struct ListNode* reverseList(struct ListNode* head)
//    {
//        //创建两个指针
//        struct ListNode* cur = head;
//        struct ListNode* newhead = NULL;
//        while (cur)
//        {
//            // 创建下一个节点  让他始终等于cur的下一个节点
//            struct ListNode* next = cur->next;
//            //头插
//            cur->next = newhead;
//            newhead = cur;
//            cur = next;
//        }  //类似一个新链表  然后后续next指针修改指向  
//        return newhead;
//    }
//
//    bool chkPalindrome(ListNode* A) {
//        //运用结构体指针  需要带上struct  因为没有重命名
//        struct ListNode* mid = middleNode(A);      //中间节点
//        struct ListNode* rmid = reverseList(mid);   //转置
//        while (A && rmid)   //两个指针有一个为空就结束比较  一个是指向原链表的初始值  一个是从中间开始往后 
//        {
//            if (rmid->val != A->val)
//            {
//                return false;
//            }
//            rmid = rmid->next;
//            A = A->next;
//        }
//        return true;
//    }
//};


//相交链表
//给两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点，如果两个链表不存在相交节点，返回NULL（单链表  一个节点只有一个next）
/*
    判断是否相交：判断尾指针 用地址进行判断
找第一个相交节点：
    思路一：A链表的节点依次和B链表所有节点比较  A某个节点跟B链表某个节点相等  那么这个节点就是交点
    （时间复杂度：O(M*N) 一个链表M个元素一个N个/   O(N^2)每个链表都是N个元素）
    思路二：时间复杂度O(N)  找到距离尾结点相同的距离的位置  均依次往后寻找进行比较  找到相同的节点  (次数：最后一次同时走故应是3N)
*/

/*
  Definition for singly-linked list.
  struct ListNode {
      int val;
      struct ListNode *next;
  };
*/
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
//{
//    //相交判断尾指针  注意需要用尾指针地址判断  不能用节点值进行判断
//    struct ListNode* curA = headA, * curB = headB;    //先定义两个指针指向头A  头B
//    //定义两个链表的长度变量
//    int lenA = 0;
//    int lenB = 0;
//    // 均进行找尾  看尾结点是否相同
//    while (curA->next)
//    {
//        curA = curA->next;
//        ++lenA;
//    }
//    while (curB->next)
//    {
//        curB = curB->next;
//        ++lenB;    //实际结果比真正长度少1   因为循环在尾结点的下一个节点为空时就没有进去
//    }
//    //尾结点不相等的情况  不相等就不相交
//    if (curA != curB)
//        return NULL;
//    //相交
//    //让长的先走  走相差的步数  再同时走  第一个相等的就是交点
//    //运用假设法
//    int gap = abs(lenA - lenB);  //假设A>B  确定差值  A-B的绝对值
//    struct ListNode* LongList = headA, * ShortList = headB;
//    //判断错误就进行更改  把长的头结点指针赋给LongList  短的头结点指针赋给ShortList
//    if (lenB > lenA)
//    {
//        LongList = headB;
//        ShortList = headA;
//    }
//    //后续就可以用长的链表先走   到此就不用关心到底谁是长链表
//    while (gap--)
//    {
//        LongList = LongList->next;
//    }
//    //开始同时向后走
//    while (LongList != ShortList)
//    {
//        LongList = LongList->next;
//        ShortList = ShortList->next;
//    }
//    //后面一样长  碰到相等的节点返回LongList和ShortList都一样
//    return ShortList;
//}